package main

import (
	"fmt"
)
/*
	给定一个数组nums，编写一个函数将所有0移动到数组末尾，同时保持非零元素的相对顺序
	必须在原数组上操作，不能拷贝额外数组
	尽量减少操作次数
*/

func moveZeros(nums []int){
	//两个指针，一个指向第一个zero元素，另一个从zero之后循环数组
	//当指向的元素非零时，将其与zero调换位置
	//n := len(nums)
	//pZero :=0
	//for i:=0;i<n;i++{
	//	if nums[i]==0{
	//		pZero = i
	//		//非零元素不处于最后一项
	//		if pZero < n-1{
	//			for j:=pZero+1;j<n;j++{
	//				if nums[j]!=0{
	//					nums[pZero],nums[j] = nums[j],nums[pZero]
	//					pZero=j
	//				}
	//			}
	//		}
	//	}
	//}

	//答案思路跟我是一样的，但是写的更elegant
	//left指针指向已处理好的序列结尾，即零元素已经到最后，right指针指向未处理的序列开头
	//优点是通过一个if判断，让left可以指向零元素
	//left,right,n := 0,0,len(nums)
	//for right<n{
	//	if nums[right]!=0{
	//		nums[right],nums[left] = nums[left],nums[right]
	//		left++
	//	}
	//	right++
	//}

	//看到另一种解法
	//首先遍历数组，记录每个非零数字之前有几个零
	//将非零数字前移零数，再在后面补上零的个数
	n := len(nums)
	zeros := 0
	zeronums := make([]int,n)
	//遍历数组，数出一共多少零
	for i:=0;i<n;i++ {
		if nums[i]==0{
			zeros++
		}else{
			zeronums[i] = zeros
		}
	}
	for j:=0;j<n;j++ {
		if nums[j]==0{
			continue
		}else{
			nums[j-zeronums[j]] = nums[j]
		}
	}
	//从后到前补0
	for k:=n-1;k>=n-zeros;k--{
		nums[k]=0
	}
	for _,v := range nums{
		fmt.Print(v)
		fmt.Print(" ")
	}
}

func main(){
	nums := []int {0,1,0,3,12}
	moveZeros(nums)
}
